import java.util.*;

public class Dynamic_Programming {
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        Map<Integer, Integer> map = new HashMap<>();
        map.put(1, 0);
        list.add(1);
        list.add(2);
        list.add(3);
        System.out.println(map.get(1));
        list.remove(map.get(1));
        System.out.println(list);
    }


    // 动态规划专栏 Dynamic programming

    /**
     * 正则表达式匹配
     */

    /**
     * 通配符匹配
     * 给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：
     * '?' 可以匹配任何单个字符。'*' 可以匹配任意字符序列（包括空字符序列）。
     * 动态规划
     * boolean dp[i][j]表示的是在0-j个p字符串能否匹配0-i个s字符串 dp[s][p]有
     * if p == abc..
     *  dp[i][j]=true&&dp[i-1][j-1]
     * if p == ?
     *  dp[i][j]=true&&dp[i-1][j-1]
     * if p == *
     *  dp[i][j]=dp[i][j-1]||dp[i-1][j]
     * 为*那么就可以匹配任意个字符
     * p匹配零个s dp[i][j]=dp[i][j-1]   一个 dp[i][j]=dp[i-1][j-1]  二个 dp[i][j]=dp[i-2][j-1]。。。
     * 那dp[i][j]=dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]... 如果要这样循环下去遍历的话时间复杂度在n^3了
     * 优化
     * dp[i-1][j]=dp[i-1][j-1]||dp[i-2][j-1]...这和dp[i][j]的第二项往后是相同的那么就可以替换
     * 所以dp[i][j]=dp[i][j-1]||dp[i-1][j]
     * 初始化
     * 使用空字符来对齐坐标映射
     * 对于第一行第一列的初始化也要考虑，第一行是s为空的字符串，p只有*可以匹配空字符串，初始化第一行的时候
     * 从左到右，为*就是true，否这为false之后的初始化都为false
     * 第一列的话，p为空，什么s都匹配不了，就全部为false除了dp[0][0]
     */

    public static boolean isMatch(String s, String p) {
        s = "_" + s;
        p = "_" + p;

        int m = s.length();
        int n = p.length();

        char[] pp = p.toCharArray();
        char[] ss = s.toCharArray();

        boolean[][] dp = new boolean[m][n];

        dp[0][0] = true;
        for (int i = 1; i < n; i++) {
            if (pp[i] == '*') dp[0][i] = true;
            else break;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (pp[j] == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pp[j] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else if (pp[j] == ss[i]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 不同的子序列
     * 给一个s好t字符串，放回s的子序列为t的个数 将结果对 10^9 + 7 取模
     * 动态规划
     * 定义dp[i][j]表示的是t在0-j这个区间的所有子序列中，等于t 0-i子串的数量
     * 那么对于 t[i],d[j]这个位置的字符有
     * t[i]==s[j]
     *  dp[i][j]=dp[i-1][j-1]+dp[i][j-1]
     *  因为相同了之后只是在之前的子串上加了个字符，并没有创造出新的子串，所以并不需要加1，然后加上dp[i][j-1]是没有加上这个字符的等于0-i这个区间的子序列数目
     * t[i]!=s[j]
     *  dp[i][j]=dp[i][j-1] 那么就是不加上这个字符的在这个区间的最大的数据
     * 初始化
     * 加个字符防止越界 并把第一行全部初始化为1 因为都是相同的
     */
    public static int numDistinct(String s, String t) {
        s = "_" + s;t = "_" + t;
        int m = t.length();
        int n = s.length();

        int[][] dp = new int[m][n];

        Arrays.fill(dp[0], 1);

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (t.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
                } else {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    public static void maiNumD(String[] args) {
        System.out.println(numDistinct("babgbag", "bag"));
        System.out.println("hhh");
    }
    /**
     * 不相交的线
     * 给俩个数组，俩数组中相同的数据可以连线，每个数字只能连一根线，线于线之间不可以相交，放回线的最多的数目
     * 动态规划
     * dp[i][j]表示的是俩数组分别以i j结尾的不相交的线的最大值，那么就有
     * if(n[i]=n1[j])
     *   dp[i][j]=dp[i-1][j-1]+1
     * else
     *   for (0-j) find max(j)->n[i]=n1[j]
     *      dp[i][j]=1+dp[i-1][j-1]
     *   dp[i][j]=max([i-1][j],[i][j]) 有可能j后面后没有数，那么就去i-1,j这最大的范围的dp值
     * 要使用i-1 和j-1位置的来跟新i j，填表顺序为从上往下 从左往右
     * 多初始化一行一列来防止越界
     */
    public static int maxUncrossedLines(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[][] dp = new int[n+1][m+1];

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                if (nums1[i-1] == nums2[j-1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    for (int k = j - 1; k >= 1; k--) {
                        if (nums1[i-1] == nums2[k-1]) {
                            dp[i][j] = dp[i - 1][k - 1] + 1;
                            break;
                        }
                    }
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                }
            }
        }
        return dp[n][m];
    }

    public static void mainMaxUn(String[] args) {
        List<String> list = List.of("hhh", "hhh", "xxx");
        System.out.println(maxUncrossedLines(new int[]{1, 4, 2}, new int[]{10, 5, 2, 1, 5, 2}));
        System.out.println(maxUncrossedLines(new int[]{2, 5, 1, 2, 5}, new int[]{10, 5, 2, 1, 5, 2}));
    }

    /**
     * 最长公共子序列
     * 给俩个字符串，返回每个字符串中的最长的子序列的长度
     * 动态规划 预处理
     * 使用map<c,I>来绑定元素下标，dp[i]表示i位置结尾的最长的子序列 这个只能表示一个子序列的长度
     * 所以dp[i]应该是以i位置元素结尾的最长的子序列
     * 动态规划
     * 使用dp[i][j]来表示俩个字符串从0-i和0-j这个区间中的最长的子序列长度
     * 那么对于s[i] s[j]有
     * if s[i]=s[j] dp[i][j]=dp[i-1][j-1]+1 因为最长的一定是以这俩个为结尾的
     * if s[i]!=s[j] 那么就需要在这之中找到一个最长的子序列
     * max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
     * 前俩个其实包含了后一个情况，那么可以忽略[i-1][j-1]，应为是找到最长的，所以重复的其实是没有影响的
     * 初始化
     * 因为有i-1 j-1 所以需要多创建一行来防止越界，还可以给字符串多加一个前缀，这样1位置就对应的是1了
     * 填表
     * 从上到下 从左往右
     */
    public static int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length(); int m = text2.length();
        text1 = " " + text1; text2 = " " + text2;
        char[] t1 = text1.toCharArray();
        char[] t2 = text2.toCharArray();

        int[][] dp = new int[n+1][m+1];

        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < m+1; j++) {
                if (t1[i] == t2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][m];
    }


    public static void mainLongestCommon(String[] args) {
        System.out.println(longestCommonSubsequence("abcde", "ace"));
        System.out.println(longestCommonSubsequence("abc", "def"));
        System.out.println(longestCommonSubsequence("bl", "yby"));
    }
    /**
     * 让字符串成为回⽂串的最⼩插⼊次数
     * 动态规划
     * 定义dp[i][j]表示是i-j为回文字符串的最少插入次数
     * 那么就有
     * if i==j dp[i][j]=0
     * if i+1=j
     *   s[i]=s[j] dp[i][j]=0
     *   s[i]!=s[j] dp[i][j]=1
     * if i+1<j
     *   if s[i]=s[j] dp[i][j]=dp[i+1][j-1]
     *   if s[i]!=s[j] dp[i][j]=min(dp[i][j-1]+1,1+dp[i+1][j])
     * 因为是要使用[i][j-1],[i+1][j]来跟新[i][j]所以填表顺序是从下往上，从左往右 j>=i
     */
    public static int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        char[] c = s.toCharArray();

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (c[i] == c[j]) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : 0;
                } else {
                    dp[i][j] = i + 1 < j ? Math.min(dp[i + 1][j], dp[i][j - 1]) + 1 : 1;
                }
            }
        }
        return dp[0][n - 1];
    }

    public static void mainNinI(String[] args) {
        System.out.println(minInsertions("abc"));
        System.out.println(minInsertions("mbadm"));
        System.out.println(minInsertions("leetcode"));
        System.out.println(minInsertions("ccewnxhytsr"));

    }
    /**
     * 回文串分割II
     * 给一个字符串，将他分割为若干个子串，返回最小的分割数
     * 动态规划
     * 先把所有的回文储存在dp中
     * 使用递归来遍历所有的可能 dp[i][j]=t -> dp[j+1][k]=t >... 递归超时
     * 使用map 来储存回文串下标map<Integer,List<Integer>> 这这样只需要遍历一遍就好，且少了很多不必要的false判断 还是超时 最坏情况下会有n层递归
     * 动态规划来解决
     * 使用count[i]来表示从0-i的回文串最少分割数，那么就有
     * 0-i 是回文串  --> 0
     * else
     * for j (1->= i) 可以自己也分割为一个
     * find (dp[j][i]) min(count[j-1])  如果是回文串，就在前面找到一个最少的分割数，在加上最后j i这个回文串
     * dp[i]=min
     * 预处理优化 先储存所有回文串的信息
     * 从左往填表
     */


    public static int minCut(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[n][n];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (chars[i] == chars[j]) {
                    dp[i][j] = i + 1 >= j ? true : dp[i + 1][j - 1];
                }
            }
        }

        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            if (dp[0][i]) {
                count[i] = 0;
            } else {
                int min = 2001;
                for (int j = 1; j <= i; j++) {
                    if (dp[j][i]) {
                        min = Math.min(min, count[j-1]+1);
                    }
                }
                count[i] = min;
            }
        }
        return count[n - 1];
    }

    public static void mainMinCut(String[] args) {
        System.out.println(minCut("b"));
//        System.out.println(minCut("\"apjesgpsxoeiokmqmfgvjslcjukbqxpsobyhjpbgdfruqdkeiszrlmtwgfxyfostpqczidfljwfbbrflkgdvtytbgqalguewnhvvmcgxboycffopmtmhtfizxkmeftcucxpobxmelmjtuzigsxnncxpaibgpuijwhankxbplpyejxmrrjgeoevqozwdtgospohznkoyzocjlracchjqnggbfeebmuvbicbvmpuleywrpzwsihivnrwtxcukwplgtobhgxukwrdlszfaiqxwjvrgxnsveedxseeyeykarqnjrtlaliyudpacctzizcftjlunlgnfwcqqxcqikocqffsjyurzwysfjmswvhbrmshjuzsgpwyubtfbnwajuvrfhlccvfwhxfqthkcwhatktymgxostjlztwdxritygbrbibdgkezvzajizxasjnrcjwzdfvdnwwqeyumkamhzoqhnqjfzwzbixclcxqrtniznemxeahfozp\""));
    }

    //hash优化overtime 递归的问题
    static int MinMinCut = 2001;

    private static void dfsMinTooDeep(int s, int n, Map<Integer, List<Integer>> map, boolean[][] dp, int count) {
        if (s < n && dp[s][n-1]) {
            MinMinCut = Math.min(MinMinCut, count);
            return;
        }
        List<Integer> list = map.get(s);
        if (list == null) {
            return;
        }
        for(Integer i : list) {
            dfsMinTooDeep(i+1,n, map,dp, count + 1);
        }
    }

    private static void dfsMinOverTime(int r, boolean[][] dp, int count, int n) {
        if (r < n && dp[r][n - 1]) {
            MinMinCut = Math.min(MinMinCut, count);
            return;
        }
        for (int i = r; i < n; i++) {
            if (dp[r][i]) {
                dfsMinOverTime(i + 1, dp, count + 1, n);
            }
        }

    }


    /**
     * 回文串分割IV diff
     * 如果一个字符串可以分割为3个回文串的话，那么就返回true
     * 动态规划
     * 使用一个二维dp[i][j]表来表示i-j是否是回文串
     * if n[i] = n[j]
     * dp[i][j] = i+1<j?true:dp[i+1][j-1]
     * 从下往上从左往右
     * 然后再根据这个表来判断是否是可以分为三个
     * 遍历三次来检查是否可以分割
     */
    public static boolean checkPartitioning(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[n][n];
        Map<Integer,List<Integer>> map = new HashMap<>();

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (chars[i] == chars[j]) {
                    dp[i][j] = i + 1 >= j ? true : dp[i + 1][j - 1];
                }
                if (dp[i][j]) {
                    List<Integer> list = map.getOrDefault(i, new ArrayList<>());
                    list.add(j);
                    map.put(i, list);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (dp[0][i]) {
                List<Integer> list1 = map.get(i+1);
                for(Integer j : list1) {
                    if (dp[j + 1][n - 1]) {
                        return true;
                    }
                }
            }
        }

//        for (int j = 0; j < n; j++) {//第一段
//            if (dp[0][j]) {
//                for (int k = j + 1; k < n; k++) {//第二段 j+1，k
//                    if (dp[j + 1][k] && k + 1 < n && dp[k + 1][n - 1]) {//第三段k+1，n-1
//                        return true;
//                    }
//                }
//            }
//        }
        return false;
    }


    public static void mainCheck(String[] args) {
        System.out.println(checkPartitioning("bcbddxy"));
        System.out.println(checkPartitioning("abcbdd"));
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        int[] arr = new int[3];
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 2;
        System.out.println(list.toString());
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 最长回文串
     * 返回最长的回文串
     * 要的到回文串，就要先知道回文有哪些，那么就可以使用dp[i][j]来得到哪些是回文串，在count[i][j]来记录着个回文串的长度
     * do[i][j]表示这个i j这个区域是否是回文串
     * if s[i]==s[j]
     * dp[i][j] = i+1< j?true: dp[i+1][j-1]
     * count[i][j] += dp[i][j]?count[i+1][j-1]+2:0;
     * 使用i j来记录最大长度的位置
     * 使用i+1和j-1位置的dp表来填表，那么填表顺序时从下往上从左往右
     * <p>
     * i j 其实已经储存了位置信息所以其实不需要专门在搞个表来记录长度
     */
    public static String longestPalindrome(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[n][n];
        int[][] count = new int[n][n];
        int ret = 1;
        int[] lr = new int[2];

        // i < j
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (chars[i] == chars[j]) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;

                    if (dp[i][j])
                        count[i][j] = i + 1 <= j ? count[i + 1][j - 1] + 2 : 1;

                    if (count[i][j] > ret) {
                        ret = count[i][j];
                        lr[0] = i;
                        lr[1] = j;
                    }
                }
            }
        }
        return s.substring(lr[0], lr[1] + 1);
    }

    public static void mainLongEst(String[] args) {
        System.out.println(longestPalindrome("cbbd"));
        System.out.println(longestPalindrome("babad"));

    }

    /**
     * 回文子串
     * 返回字符串中的所有回文子串的数目
     * 递归
     * 使用使用递归来判断i j结尾的字符串是否是回文串，是的话就给加加，不是就不管
     * 动态规划
     * dp[i][j] 来表示这个位置结尾的是否为回文串，使用功能dp来优化递归
     * dp[i][j]=0表示没计算 通过递归来计算
     * dp[i][j]=1表示是 =2不是
     * 2. 使用bool dp[i][j]
     * dp[i][j]表示ij这个区域是否是回文串 i < j
     * if(n[i] = n[j])
     * if(i==j||j+1==i) dp[i][j] = true
     * else dp[i][j] = dp[i+1][j-1]
     * 填表顺序
     * 需要i+1位置的来根性i位置的值，那么应该是从下往上来更新
     */
    public int countSubstrings(String s) {
        int n = s.length();
        int ret = 0;
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[n][n];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (chars[j] == chars[i]) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                    ret += dp[i][j] ? 1 : 0;
                }
            }
        }
        return ret;
    }

    public int countSubstringsByDpDfs(String s) {
        int n = s.length();
        int ret = 0;
        char[] chars = s.toCharArray();

        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (chars[i] == chars[j]) {
                    if (dp[i - 1][j + 1] == 0) {//计算i-1 j+1
                        dp[i][j] = dfsCount(chars, i - 1, j + 1) ? 1 : 2;
                        ret += dp[i][j] == 1 ? 1 : 0;
                    } else {
                        dp[i][j] = dp[i - 1][j + 1];
                        ret += dp[i][j] == 1 ? 1 : 0;
                    }
                }
            }
        }
        return ret + n;
    }


    //递归
    public int countSubstringsDfs(String s) {
        int n = s.length();
        int ret = 0;
        char[] chars = s.toCharArray();

        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (chars[i] == chars[j]) {
                    ret += dfsCount(chars, i - 1, j + 1) ? 1 : 0;
                }
            }
        }
        return ret + n;
    }

    //判断j i 这段是否是回文串
    private boolean dfsCount(char[] chars, int i, int j) {
        if (j >= i) {
            return true;
        }
        if (chars[i] == chars[j]) {
            return dfsCount(chars, i - 1, j + 1);
        }
        return false;
    }

    public void maincountS(String[] args) {
        System.out.println(countSubstrings("aaa"));
    }

    /**
     * 等差序列划分II diff
     * 返回所有等差子序列的数目
     * 动态规划
     * 定义dp[i][j]表示以i j结尾的子序列的数目，且i<j
     * 如果在前面满足 v= 2*nums[j] - nums[i]
     * dp[i][j] += dp[j][k] + 1
     * 其他情况都为0
     * 优化
     * 使用一个hash表来储存值和小标们
     * 填表
     * 固定i 往前遍历j
     * 会有大数相加超过int的，在计算的时候给每个数转换为long
     */

    public int numberOfArithmeticSlicesII(int[] nums) {
        int n = nums.length, ret = 0;
        int[][] dp = new int[n][n];

        HashMap<Long, List<Integer>> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            List<Integer> list = map.getOrDefault((long) nums[i], new ArrayList<>());
            list.add(i);
            map.put((long) nums[i], list);
        }

        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                long v = (long) nums[j] - ((long) nums[i] - (long) nums[j]);
                if (map.containsKey(v)) {
                    List<Integer> list = map.get(v);
                    for (int in : list) {
                        if (in < j) {
                            dp[i][j] += dp[j][in] + 1;
                        }
                    }
                    ret += dp[i][j];
                }
            }
        }
        return ret;
    }

    public void mainNumII(String[] args) {
        System.out.println(numberOfArithmeticSlicesII(new int[]{2, 4, 6, 8, 10}));
        System.out.println(numberOfArithmeticSlicesII(new int[]{7, 7, 7, 7, 7}));
        System.out.println(numberOfArithmeticSlicesII(new int[]{0, 2000000000, -294967296}));
        System.out.println(Integer.MAX_VALUE > 2000000000);
        System.out.println(Integer.MIN_VALUE < -294967296);
        int s = -294967296 - 2000000000;
        System.out.println(s);
        long t = -2147483648L * 2;
        System.out.println(t);
        System.out.println(-2147483648 * 2);
        System.out.println((long) -2147483648);
        System.out.println((long) 3);
        System.out.println((long) -2);

    }

    /**
     * 最长等差数列
     * 给一个数组，返回这个数组中最长的等差序列的长度
     * 动态规划
     * 使用dp[i][j]表示以i，j，i>j,结尾的最长的等差数组，只需要知道了i j俩个位置的那么就能往前一直推
     * dp[i][j] 表示的是差值为n[i]-n[j]的子序列数组的最长的长度
     * if have(n[k]-(n[j]-n[k]))
     * dp[i][j] = dp[j][k]+1
     * else
     * 2
     */
    public int longestArithSeqLengthHash(int[] nums) {
        //使用了hash优化同时填表方向改变了，不然过不了 i 在前 j在后 因为是固定的倒数第二个元素，那么在这个之前的hash表其实不会引起冲突
        //问题的，他的index都是最新跟新的而如果是固定的是第一个 那么在加入到hash表中的时候j是在前遍历找到hash中到，那么就会发现某些情况已经被覆盖了
        //而这时的是错误的值
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(nums[0], 0);

        int n = nums.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], 2);
        }

        int ret = 2;
        for (int i = 1; i < n; i++) { //i是倒数第二哥元素
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = 2;
                int v = 2 * nums[i] - nums[j];
                if (map.containsKey(v)) {
                    dp[i][j] = dp[map.get(v)][i] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }
            }
            map.put(nums[i], i);
        }
        return ret;
    }

    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        int ret = 2;

        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                dp[i][j] = 2;
                int v = nums[j] - (nums[i] - nums[j]);//有错是因为忽略了相同的情况。在相同的情况下使用map会出错
                for (int k = j - 1; k >= 0; k--) {
                    if (nums[k] == v) {
                        dp[i][j] = dp[j][k] + 1;
                        ret = Math.max(ret, dp[i][j]);
                        break;
                    }
                }
            }
        }
        return ret;
    }

    public void mainLong(String[] args) {
        System.out.println(longestArithSeqLengthHash(new int[]{44, 46, 22, 68, 45, 66, 43, 9, 37, 30, 50, 67, 32, 47, 44, 11, 15, 4, 11, 6, 20, 64, 54, 54, 61, 63, 23, 43, 3, 12, 51, 61, 16, 57, 14, 12, 55, 17, 18, 25, 19, 28, 45, 56, 29, 39, 52, 8, 1, 21, 17, 21, 23, 70, 51, 61, 21, 52, 25, 28}));
    }

    /**
     * 最长斐波那契子序列的长度
     * 给一个数组，返回其中的最长的满足斐波那契子序列，n[i]=n[i-1]+n[i-2]
     * 动态规划
     * 因为需要俩个数才能推出第三个数，那么反过来，我知道了最后的俩个数，就可以把这整个数组推出来
     * 所以可以使用二维dp表来进行计算 dp[i][j] 表示的是以i，j结尾的最长的子序列，i>j,那么有
     * if n[i]-n[j] == n[k] && k < j
     * dp[i][j] = dp[j][k]+1
     * else 不存在 （或者大于了j||i 因为这样就不符合dp定义了）
     * dp[i][j] = 2
     * 先遍历一遍arr 将信息储存在hash中，从前往后变遍历
     */
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            map.put(arr[i], i);
        }

        int ret = 0;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                int v = arr[i] - arr[j];
                if (map.containsKey(v) && map.get(v) < j) {
                    int i1 = map.get(v);
                    dp[i][j] = dp[j][i1] + 1;
                    ret = Math.max(ret, dp[i][j]);
                } else {
                    dp[i][j] = 2;
                }
            }
        }
        return ret == 2 ? 0 : ret;
    }

    public void mainLenLong(String[] args) {
        System.out.println(lenLongestFibSubseq(new int[]{1, 2, 3, 4, 5, 6, 7, 8}));
    }

    /**
     * 最长定差子序列
     * 给一个一维数组和diff，放回元素之间的差为diff的最长子序列
     * 动态规划
     * 使用一个dp[i]来表示以i位置为结尾的最长的子序列
     * right
     * 使用一个dp[i]来表示以i位置为结尾的所有子序列中最长的子序列
     * 因为知道了i的元素和diff，那么也能知道i-1的数字应该是多大，那么只需要在前面找到最近的这个数的位置
     * dp[i] = 1 if not exist
     * else dp[i] = dp[j]+1
     */
    public int longestSubsequence(int[] arr, int difference) {
        int n = arr.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        int ret = 1;
        for (int i = 0; i < n; i++) {
            int v = arr[i];
            if (map.containsKey(v - difference)) {
                int dp = map.get(v - difference) + 1;
                ret = Math.max(ret, dp);
                map.put(v, dp);
            } else {
                map.put(v, 1);
            }
        }
        return ret;
    }

    public int longestSubsequenceOverTime(int[] arr, int difference) {
        int n = arr.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[i] - arr[j] == difference) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    max = Math.max(max, dp[i]);
                }
                if (dp[i] > j) {
                    break;
                }
            }
        }
        return max;
    }

    public void mainLongest(String[] args) {
        System.out.println(longestSubsequence(new int[]{1, 5, 7, 8, 5, 3, 4, 2, 1}, -2));
    }

    /**
     * 最长数对链
     * 给一个二维数组，其中的arr[i] 中的r固定大于l，如果满足 l[i] > r[i-1]那么就可以把这个俩个数组结合起来返回最长的长度
     * 动态规划 + 预处理
     * 将数组按照r来升序排序，这样在使用l进行比较r的时候只需要往前遍历就行
     * 定义dp[i]表示以i结尾的最长的数对联 j (0-i-1)
     * if(r[i] > l[j])
     * dp[i] = max(dp[i],dp[j]+1)
     * ret = max(dp[i],ret)
     * 小于不管
     */
    public int findLongestChain(int[][] pairs) {
        int n = pairs.length;
        Arrays.sort(pairs, (i, j) -> {
            return i[1] - j[1];
        });
        for (int[] i : pairs) {
            System.out.println(Arrays.toString(i));
        }
        int[] dp = new int[n];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (pairs[i][0] > pairs[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    max = Math.max(max, dp[i]);
                }
            }
        }
        return max;
    }

    public void mainFindLong(String[] args) {
        System.out.println(findLongestChain(new int[][]{{1, 2}, {2, 3}, {3, 4}}));
    }

    /**
     * 最长递增子序列的个数
     * 给一个数组，放回其中的最长的严格递增子序列的个数，在选择时只需要保证元素先后顺序没破坏就行
     * 动态规划
     * 使用一个二维的dp表dp[i][2]
     * dp[i][0]表示以i结尾的元素的最长的子序列数组，dp[i][1]表示的从0-i有长度为dp[i][0]的子序列数组个数
     * max记录最长的数组 index 对应的dp[i]数组位置 j往前遍历nums来找到最大的子序列数组
     * dp[i][0] = dp[j][0]+1,dp[i][1]=dp[j][1]
     * if [i][0] == max && i!= index
     * dp[i][1] += dp[index][1] err难写 但是思路是对的，把这来个表分开好写些
     * right
     * 使用俩个表，
     * len[i]表示的是以i这个位置为结尾的最长的子序列数组长度
     * count[i]表示的额是以i为结尾的最长的子序列数组个数
     * 对于nums[i]就有
     * 在0-i中找到
     * nums[j]<nums[i]
     * 这时的nums[i]的值有三种情况
     * len[j]+1 == len[i]  -->  count[i]+=count[j] 这时的i能插入到j结尾的数组中，这个j结尾的数组的个数在count[j]中
     * len[j]+1 > len[i] -->  len[i] = len[j]+1,count[i]=count[j] 因为这时跟新了nums[i]的值，但是不意味着这个数组的个数为1，
     * 而是count[j]结尾的值，因为是挂在count[j]结尾
     * nums[i] +1 < nums[i] --->   不管
     * 这样填下来 len中储存了以i结尾的长度  count记录了这个长度的数组的个数
     * 在填表的时候可以使用来俩个变量 mL和mC来储存最长的和最最长的个数
     * 在有 len[i] > ml   ml = len[i]  mC = count[i]
     * len[i]==ml  mC +=count[i]
     * 放回mC
     */
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] len = new int[n];
        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            len[i] = 1;
            count[i] = 1;
        }
        int max = 1, maxCount = 1;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    if (len[j] + 1 == len[i]) {
                        count[i] += count[j];
                    } else if (len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }
            if (max == len[i]) {
                maxCount += count[i];
            } else if (max < len[i]) {
                max = len[i];
                maxCount = count[i];
            }
        }
        return maxCount;
    }

    public void mainFindNum(String[] args) {
//        System.out.println(findNumberOfLIS(new int[]{0,1,0,3,2,3}));
        System.out.println(findNumberOfLIS(new int[]{1, 3, 5, 4, 7}));
        System.out.println(findNumberOfLIS(new int[]{2, 2, 2, 2, 2}));
    }

    /**
     * 最长递增子序列
     * 放回一个数据中的最长的递增子串长度
     * 动态规划
     * 定义dp[i]表示的是i位置为结尾的最长的递增子串长度，那么在dp[i]是一个递增的，当n[i]大于dp[i]时，
     * 可以直接将尾插到dp中，但如果是小于最后的一个数的话，那么就要在前面找到一个合适的位置，并替换这个位置的数
     * 这个位置的前一个数小于他，，后一个数大于他，而n[i]插入了这个位置，并不会对被修改的这个数有什么影响，比如 3 5 6，要插入一个4
     * 那么就把5替换为4变为 3 4 6，这里的5其实是包含了4的情况，所以这样等到将这个n遍历一遍之后，就可以找出最长的递增数组了，但是这个数组只是
     * 大小正确，而数字的顺序其实是已经改变了的
     * if n[i] > dp[i]
     * add(n[i])
     * else
     * find(n[j-1]<n[i]&&n[j+1]>n[i]) ：这里的i-1~i+1就代表了i这个位置能插入值的范围，那么插入这个范围的数就都不会对数组有什么影响
     * 在找打插入位置的时候可以二分优化查找，因为数组是可以严格分为俩半的
     * set(j,n[i])
     */
    public int lengthOfLIS2(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    max = Math.max(max, dp[i]);
                }
            }
        }
        return max;
    }

    public int lengthOfLIS(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            if (nums[i] > list.get(list.size() - 1)) {//比所有的都大
                list.add(nums[i]);
            } else {//二分找到插入位置 找到j nums[i]>nums[j-1] nums[i]<=nums[j] 然后将j值 变为i值
                int left = 0;
                int right = list.size() - 1;
                while (right > left) {
                    int mid = left + (right - left) / 2;
                    if (list.get(mid) < nums[i]) {//target大于,mid往右走
                        left = mid + 1;
                    } else {//target小于等于都往左走
                        right = mid;
                    }
                }
                list.set(left, nums[i]);
            }
        }
        return list.size();
    }

    public void mainLength(String[] args) {
        lengthOfLIS(new int[]{10, 9, 2, 5, 66, 3, 7, 101, 18});
    }

    /**
     * 环绕字符串中唯一的子字符串
     * 定义一个无限循环的字符串str： z abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz a
     * 给一个字符串，返回这个字符串来这个字符串中有多少个子串是在这个定义的字符串中
     * 环形字符串寻找
     * 动态规划
     * 定义dp[i]为i位置结尾的字符串在str中出现的次数，并且不会这个字符串不会包括自己的情况，这样就可以避免多加的情况 不行还可能有多个字符串都存在的情况
     * 那么就需要储存所有的字符串的可能 List<List<String>>,每次加上前面的所有情况
     * 那么对于dp[i]位置的就有
     * if(s[i] == s[i-1])
     * new list.add(dp[i-1].all+s[i])
     * dp[list]
     * else if(s[i]==a&&s[i-1]==z)
     * new list.add(dp[i-1].all+s[i])
     * dp[list]
     * else
     * new list.add()
     * dp[list]  overtime
     * right：
     * if ((cs[i] == cs[i - 1] + 1 ) || (cs[i] == 'a' && cs[i - 1] == 'z')) {
     * dp[i] = 1+dp[i-1]
     * else
     * dp[i] = 1
     * 返回值需要去重，创建一个26位长的数组用来储存每个字符结尾的字符串的最大的值，那么最后给这个表中的值相加就好
     */
    public int findSubstringInWraproundString(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        int[] charIndex = new int[26];
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        charIndex[cs[0] - 'a'] = 1;
        for (int i = 1; i < n; i++) {
            if ((cs[i] == cs[i - 1] + 1) || (cs[i] == 'a' && cs[i - 1] == 'z')) {
                dp[i] = 1 + dp[i - 1];
                charIndex[cs[i] - 'a'] = Math.max(charIndex[cs[i] - 'a'], dp[i]);
            } else {
                charIndex[cs[i] - 'a'] = Math.max(charIndex[cs[i] - 'a'], 1);
            }
        }
        int ret = 0;
        for (int i : charIndex) {
            ret += i;
        }
        return ret;  //ret多加了，在每次跟新了dp的时候要重新算下ret,是在ret上更改，而不是dp
    }

    public void mainFindSub(String[] args) {
        System.out.println(findSubstringInWraproundString("zaba"));// z za b ab zab a
    }

    //优化 对于dp[i-1]之前的就可以不用了 删除 那么dp只需要一个就好
    //当dp比啊大小超过1就把第一个给删除了
    public int findSubstringInWraproundStringOvertime(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        List<List<String>> dp = new ArrayList<>();
        Set<String> set = new HashSet<>();
        List<String> l1 = new ArrayList<>();
        l1.add(cs[0] + "");
        set.add(l1.get(0));
        dp.add(l1);

        for (int i = 1; i < n; i++) {
            if ((cs[i] == cs[i - 1] + 1) || (cs[i] == 'a' && cs[i - 1] == 'z')) {
                List<String> l2 = new ArrayList<>();
                List<String> l3 = dp.get(0);

                set.add(cs[i] + "");
                l2.add(cs[i] + "");
                for (int j = 0; j < l3.size(); j++) {
                    l2.add(l3.get(j) + cs[i]);
                    set.add(l3.get(j) + cs[i]);
                }

                dp.add(l2);
                dp.remove(0);
            } else {
                List<String> l2 = new ArrayList<>();

                l2.add(cs[i] + "");
                set.add(cs[i] + "");

                dp.add(l2);
                dp.remove(0);
            }
        }
        return set.size();
    }


    /**
     * 单词拆分
     * 给一个字符串s，再给一个单词数组，如果这个单词数组中的单词能拼成字符串s，那么就放回true
     * 动态规划
     * 使用dp[i]来表示这个字符串从0到i的位置是否能被字典给拼接出来那么对于i这个位置的字符串有：
     * 将这段字符串按j分为俩部分，0-j表示一部分 j-i表示的是后一部分，那么0-j是否能被拼接出来就来dp中储存了
     * 那么这时就只需要判断j-i能否从字典中拼接出来，那么就需要从j的范围为0-i
     * dp = dp[j-1]&&(j~i).equals(wordDict)
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        char[] chars = s.toCharArray();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;//这个位置表示的是没有字符，
        for (int i = 1; i <= n; i++) {
            //分割为俩部分 前面用dp[j] 表示，后面自己判断 j从0开始分
            for (int j = 1; j <= i; j++) {
                StringBuilder sb = new StringBuilder();
                //拼接出字符串
                for (int k = j; k <= i; k++) {
                    sb.append(chars[k - 1]);
                }
                dp[i] = dp[j - 1] && isEqual(sb.toString(), wordDict);
                if (dp[i]) {
                    break;
                }
            }
        }
        return dp[n];
    }

    private boolean isEqual(String string, List<String> wordDict) {
        for (String word : wordDict) {
            if (string.equals(word)) {
                return true;
            }
        }
        return false;
    }

    public void mainWords(String[] args) {
        List<String> wordDict = new ArrayList<>();
        wordDict.add("apple");
        wordDict.add("pen");
        System.out.println(wordBreak("applepenapple", wordDict));
    }

    /**
     * 最长湍流子数组
     * 所谓湍流子数组就是对于i位置的元素，他的左右元素的比较符号翻转，j<i<k/j>i<k，这俩中情况返回最长的子数组元素个数
     * 动态规划
     * dp[i]表示以i位置为结束的最长的湍流子数组，那么对于i位置的元素有
     * if [i] = [i-1]
     * dp[i]=0
     * else if  [i-2]>[i-1]&&[i-1]<[i] || [i-2]<[i-1]>[i-2]
     * dp[i]=dp[i-1]+1
     * else
     * dp[i] = 2  pass
     * 视频题解是使用俩个dp，fn表来分别表示是以i结尾时的呈上升和呈下降时的最长的湍流子数组
     * 那么对于这俩个表就有
     * if i-1 > i 下降
     * dp[i] = 1
     * fn[i] = dp[i-1] + 1
     * else if i-1 < i  上升
     * dp[i] = fn[i-1] +1
     * fn[i] = 1
     * else
     * dp[i] = 1
     * fn[i] = 1
     */
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n];
        int max = 1;

        if (arr[0] != arr[1]) {
            dp[1] = 2;
            max = dp[1];
        }
        for (int i = 2; i < n; i++) {
            if (arr[i] == arr[i - 1]) {
                dp[i] = 0;
            } else if ((arr[i - 2] > arr[i - 1] && arr[i - 1] < arr[i]) || (arr[i - 2] < arr[i - 1] && arr[i - 1] > arr[i])) {
                dp[i] = dp[i - 1] + 1;
                max = Math.max(max, dp[i]);
            } else {
                dp[i] = 2;
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }

    public void mainMaxT(String[] args) {
        System.out.println(maxTurbulenceSize(new int[]{4, 8, 12, 16}));
    }

    /**
     * 等差数列划分
     * 返回等差数列的长度，最少要3个数的才能称为等差数列
     * 动态归还
     * 用dp[i]表示0到i这个区间，以i结尾的等差数列的和，既然i为等差数组，那么有 nums[i] - nums[i-1] = nums[i-1] - nums[i-2]
     * 如果满足上诉表达式就有
     * dp[i] = dp[i-1]+1 因为是和dp[i-1]，[i-2]成等差数列，那么也就是和i-1,i-2之间的差值是相同的，也就是是在i-1的等差子表中加一个元素
     * 那么他也就比i-1多了一种情况 所以是dp[i-1] +1
     * else
     * 0
     */
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return 0;
        }
        int[] dp = new int[n];
        int ret = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                dp[i] = dp[i - 1] + 1;
                ret += dp[i];
            } else {
                dp[i] = 0;
            }
        }
        return ret;
    }

    public void mainMunber(String[] args) {
        System.out.println(numberOfArithmeticSlices(new int[]{0, 2, 3, 4}));
    }

    /**
     * 乘积为正数的最长子数组长度
     * 返回乘积为正数最长的子数组的长度，然后返回他的长度
     * 动态规划
     * 使用来个表 dp和fn
     * dp[i]表示的是包含i这个元素的最长的正数集
     * fn[i]表示的是包含i这个元素的最长的负数数集
     * 那么对于i这个位置的数有俩情况
     * 正数 有个特俗情况 就是如果fn[i-1]为0的话，那么乘以一个正数还是为0，所以就应该要判断 为负数也是一样需要特俗判断
     * dp[i] = dp[i-1]+1
     * fn[i] = fn[i - 1] == 0 ? -1 : fn[i - 1] + 1
     * 负数
     * dp[i] = fn[i - 1] == 0 ? -1 : fn[i - 1] + 1
     * fn[i] = max(dp[i-1]+1,fn[i-1]) 这个是错的 因为他使用了前一个结尾的集合fn[i-1]这样他就不是代表的是以i这个位置为结尾的最长的的
     * fn[i] = Math.max(1, dp[i - 1] + 1);
     */
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] fn = new int[n];
        int maxLen = 0;
        if (nums[0] > 0) {
            dp[0] = 1;
            maxLen = 1;
        } else if (nums[0] < 0) {
            fn[0] = 1;
        }
        for (int i = 1; i < n; i++) {
            if (nums[i] > 0) {
                dp[i] = dp[i - 1] + 1;
                fn[i] = (fn[i - 1] == 0 ? -1 : fn[i - 1]) + 1;
                maxLen = Math.max(maxLen, dp[i]);
            } else if (nums[i] < 0) {
                dp[i] = (fn[i - 1] == 0 ? -1 : fn[i - 1]) + 1;
                fn[i] = Math.max(1, dp[i - 1] + 1);
                maxLen = Math.max(maxLen, dp[i]);
            } else {
                dp[i] = 0;
                fn[i] = 0;
            }
        }
        return maxLen;
    }

    public void mainGetM(String[] args) {
        System.out.println(getMaxLen(new int[]{9, -8, -9, 3, -10, 2}));
    }

    /**
     * 乘积最大子数组和
     * 他的数组后面的数会影响到到最终的结果，那么就不能使用以i位置为结尾来获得最大值
     * 那么就以i位置开始走到最后一个位置的最大的成绩和，也不行，也是那么前面的还是为影响到
     * 那么就使用一个二维的数组来表示状态，0为这个位置为正数1为负数，也不行,因为在i这个位置的nums[i]
     * 有可能是负数，也有可能是正数，如果是正数就需要在前面找到一个连续的最大的正数集，那么就需要乘以前面最大的
     * 为负数就乘以前面的最小的，那么就需要使用到俩个表，一个dp储存的i结尾的连续的最大的数，fn储存的是i结尾的连续的最小的数
     * 那么对与dp表就有i为一个子集，i为负数那么就要fn中找到最小的子集i-1，i为正数那么就在dp中找到一个最大的子集i-1位置
     * fn的填表也是这样
     * 那么就有
     * dp[i] = max(nums[i],dp[i-1]*nums[i],fn[i-1]*nums)
     * fn[i] = min(nums[i],dp[i-1]*nums[i],fn[i-1]*nums)
     * 最终返回dp[n]
     */
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] fn = new int[n];
        dp[0] = nums[0];
        fn[0] = nums[0];
        int ret = nums[0];
        for (int i = 1; i < n; i++) {
            int v = nums[i];
            dp[i] = Math.max(v, Math.max(dp[i - 1] * v, fn[i - 1] * v));
            fn[i] = Math.min(v, Math.min(dp[i - 1] * v, fn[i - 1] * v));
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }

    public void mainMaxP(String[] args) {
        System.out.println(maxProduct(new int[]{2, 3, -2, 4}));
    }

    /**
     * 环形子数组的最大和
     * 对于无环得情况，就是一个普通的求最大的动态规划就好，而对于左右俩边连续的情况，那么就有，左边加上右边获得的是最大的连续的数组
     * 换而言之，这中间的就是最小的连续数组，那么我就只需要找到连续的最小的数组，在减去所有的和，获得的就是左右连续的最大的，俩次dp
     * 动态规划
     * dp[i]表示以i为结尾的最大的子数组和
     * dp[i] = max(dp[i-1],0)+v[i]
     * m = max(max,dp[i])
     * fn[i]表示的就是以i为结尾的最小的子数组和
     * fn[i] = min(dp[i-1],0)+v[i]
     * min = min(min,dp[i])
     * 注意考虑下可能会有整个数组都为负数的情况，那么这是最小就会取到整个数组，那么这个情况就需要直接返回max，因为sum-min==0
     */
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < n + 1; i++) {
            sum += nums[i - 1];
            dp[i] = Math.max(dp[i - 1], 0) + nums[i - 1];
            max = Math.max(max, dp[i]);
        }
        int[] fn = new int[n + 1];
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < n + 1; i++) {
            fn[i] = Math.min(fn[i - 1], 0) + nums[i - 1];
            min = Math.min(min, fn[i]);
        }
        return Math.max(max, sum - min == 0 ? max : sum - min);
    }

    public void mainMaxS(String[] args) {
        System.out.println(maxSubarraySumCircular(new int[]{-3, -2, -3}));
    }

    /**
     * 买卖股票的最佳时机 IV diff
     * 和三唯一的差别是iv可以进行k次交易，返回这k次交易能获得的最大的利润，k次交易和2次交易都是一样的
     * 只需要在III的基础上给2次改为k次就好
     */
    public int maxProfitIV(int k, int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][k + 1];
        int[][] fn = new int[n][k + 1];
        dp[0][0] = -prices[0];
        for (int i = 1; i <= k; i++) {
            dp[0][i] = Integer.MIN_VALUE / 2;
            fn[0][i] = Integer.MIN_VALUE / 2;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < k + 1; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], fn[i - 1][j] - prices[i]);
                fn[i][j] = fn[i - 1][j];
                if (j - 1 >= 0) {
                    fn[i][j] = Math.max(fn[i][j], dp[i - 1][j - 1] + prices[i]);
                }
            }
        }
        int ret = 0;
        for (int i = 0; i <= k; i++) {
            ret = Math.max(ret, fn[n - 1][i]);
        }
        return ret;
    }

    public void mainProfitIV(String[] args) {
        System.out.println(maxProfitIV(11, new int[]{48, 12, 60, 93, 97, 42, 25, 64, 17, 56, 85, 93, 9, 48, 52, 42, 58, 85, 81, 84, 69, 36, 1, 54, 23, 15, 72, 15, 11, 94}));
    }

    /**
     * 买卖股票的最佳时机 III diff
     * 最多只能进行俩次交易，返回最大的利润，也是一次只能完成一次的交易
     * 需要记录下是否有俩次交易 那么可以是从i位置开始向后进行俩次交易能获得的最大的利润
     * 暴力解法  内存超出限制
     * 使用一个二维数组ij来表示在i位置买入，j位置卖出的利润，然后遍历这个二维数据，获得俩段最长的
     * 优化，多初始化列来记录这个位置的利润最大值，且j只需要遍历i+1的位置
     * 动态规划
     * 因为只能交易俩次，那么就需要把这些交易次数也几下，那么就多需要一维来记录下交易次数
     * 那么就是使用一个三维数组，dp[i][j][k] i表示在i天结束之后，j表示是处于那种状态，j表示的是交易次数，也可以是用俩个二维dp表来简化
     * 那么就是dp[i][j]表示的是第i天结束处于买入状态完成j比交易获得的最大利润
     * 那么就是fn[i][j]表示的是第i天结束处于卖出状态完成j比交易获得的最大利润
     * 如果j为0就能表示这一天没有进行交易
     * 状态机
     * dp[i][j] = max(dp[i-1][j],fn[i-1][j] - p[i])
     * fn[i][j] = max(fn[i-1][j],dp[i-1][j-1] + p[i]) 因为当从买入到卖出就是完成了一笔交易
     * 初始化
     * 初始化俩个表的第一排 dp[0][0]为-p[0]而在第一次的买的时候不会涉及到卖出的多次交易，但是在第二天的时候不能使用到,如果为0的话
     * 在之前会有负数的情况会被忽略而影响了之后的结果，如果直接初始化为负数的最大的话，会可能有超出整形的最大值，那么也不能直接使用整形的最小
     * 还有j小于0的情况，小于零的之后，那么他直接是fn等于上一天的结果fn[i-1][0]这也要考虑
     */
    public int maxProfitIII(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];
        int[][] fn = new int[n][3];
        dp[0][0] = -prices[0];
        dp[0][1] = Integer.MIN_VALUE / 2;
        dp[0][2] = Integer.MIN_VALUE / 2;
        fn[0][1] = Integer.MIN_VALUE / 2;
        fn[0][2] = Integer.MIN_VALUE / 2;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], fn[i - 1][j] - prices[i]);
                fn[i][j] = fn[i - 1][j];
                if (j - 1 >= 0) {
                    fn[i][j] = Math.max(fn[i][j], dp[i - 1][j - 1] + prices[i]);
                }
            }
        }
        int ret = Math.max(fn[n - 1][2], fn[n - 1][1]);
        return Math.max(ret, 0);
    }

    public int maxProfitIIIOverMemory(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][n + 1];
        for (int i = 0; i < n; i++) {
            int curM = 0;
            for (int j = i + 1; j < n; j++) {
                int val = prices[j] - prices[i];
                if (val > curM) {
                    curM = val;
                }
                dp[i][j] = Math.max(val, 0);
            }
            dp[i][n] = curM;
        }

        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int m = 0;
                for (int k = j + 1; k < n; k++) {
                    m = Math.max(m, dp[k][n]);
                }
                int profit = dp[i][j] + m;
                ret = Math.max(ret, profit);
            }
        }
        return ret;
    }

    public void mainprofitIII(String[] args) {
        System.out.println(maxProfitIII(new int[]{1, 2, 3, 4, 5}));
    }

    /**
     * 买卖股票的最佳时机含手续费
     * 有个price数组，price[i]表示的是第i天的股票价格，可以无限次的交易，但是每次交易都需要手续费fee，每次只能完成一笔交易，返回最大的利润
     * 动态规划 也是状态机
     * 有俩种状态，在第i天买入或者卖出，如果是买入那么需要减去当前的价格，如果是卖出需要加上当天的价格
     * dp[i][0]在第i天结束之后处于买入转态能获得的最大利润，dp[i][1]就是卖出
     * dp[i][0] = max(dp[i-1][1]-p[i],dp[i-1][0])
     * dp[i][1] = max(dp[i-1][0]+p[i]-fee,dp[i-1][1])
     */
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][1] - prices[i], dp[i - 1][0]);
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
        }
        return Math.max(dp[n - 1][1], dp[n - 1][0]);
    }

    /**
     * 买卖股票的最佳时机含冷冻期   状态机
     * 买入股票，在卖出，返回能赚的最大利润，每次只能完成一笔交易，在卖出之后，有一天冷却器
     * 那么就又三种状态，买入，卖出，冷却期，对这三种状态通过状态机来获得彼此之间的关系，所谓转态机就是考虑每种状态将以哪种条件来到达（i-1》i）所有的状态，包括自己
     * 以此来推出状态转移方程，那么就需要一个n*3的dp表来表示在i天结束每种状态对应的最大利润，比如0代表买入那么dp[i][0]代表在第i结束，处于买入状态对应的最大利润
     * 买入 0 卖出 1  冷却期 2  画图得
     * dp[i][0] = max(dp[i-1][0],dp[i-1][1]-price[i])
     * dp[i][1] = max(dp[i-1][1],dp[i-1][2])
     * dp[i][2] = dp[i-1][0]+price[i]
     * 初始化只需要手动将第0天给考虑，然后从第一天开始填表来防止越界
     */
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++) {
            int val = prices[i];
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - val);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + val;
        }
        return Math.max(Math.max(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
    }

    //不能多初始化一行，因为在第0天买入股票的时候收益应该为付的，而前一个位置实际上为0在赋值时也就会给为0.因为这样就导致的第0天迈股票就是白嫖了
    public int maxProfitErrByMore(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n + 1][3];
        for (int i = 1; i <= n; i++) {
            int val = prices[i - 1];
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - val);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + val;
        }
        return Math.max(Math.max(dp[n][0], dp[n][1]), dp[n][2]);
    }

    public void mainProf(String[] args) {
        maxProfitErrByMore(new int[]{1, 2, 3, 0, 2});
    }

    /**
     * 粉刷房子
     * 有n个房子，每个房子可以选择被粉刷为红，蓝，绿中的一种颜色，并且相邻的房子颜色不能相同，
     * costs[i][0]表示的是i号房子粉刷为红色的价格，放回粉刷完所有房子所需要的最小的价格
     * 动态规划
     * 因为每次涂到了i这个位置，都会有三种选择，而这三种选择都会影响我接下来的选着，那么我就可以使用一个二维数组在记录下我每次选择
     * 对应的结果，那么最后在返回是就放回这三个之中最小的
     * dp[i][0]表示的就是我i这个位置选择为红色对应的最小价格
     * 那么就有 dp[i][0] = min(dp[i-1][1],dp[i-1][2])+costs[0];
     */
    public int minCost(int[][] costs) {
        int n = costs.length;
        int[][] dp = new int[n + 1][3];
        for (int i = 1; i < n + 1; i++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][0]) + costs[i - 1][2];
        }
        return Math.min(Math.min(dp[n][0], dp[n][1]), dp[n][2]);
    }

    public void mainCost(String[] args) {
        System.out.println(minCost(new int[][]{{17, 2, 17}, {5, 5, 5}, {14, 93, 3}}));//不同有相同的
    }

    /**
     * 删除并获得点数
     * 每次可以选择获得dp[i]的值，然后删除所有的等于dp[i]-1和dp[i]+1的值，放回能获得的最大值
     * 对于i位置的值 可以选择要或者不要
     * 预处理+动态规划
     * 将nums数组映射到一个数组dp中，然后对数组dp进行一次打家劫舍就好
     */
    public int deleteAndEarn(int[] nums) {
        int[] dp = new int[10003];
        for (int i : nums) {
            dp[i + 2] += i;
        }
        for (int i = 2; i < 10003; i++) {
            dp[i] = Math.max(dp[i - 2] + dp[i], dp[i - 1]);
        }
        return dp[10002];
    }

    /**
     * 打家劫舍II
     * 队列是环形的如果要按最后一个，那么第一个就不能拿，因为是相邻的
     * 动态规划
     * 那么就是有个特殊情况 我第一个位置的拿了，那么最后一个就拿不到，第一个位置的不拿，就可以那最后一个位置的
     * 最后去着俩的最大值
     */
    public int robII(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        return Math.max(dfsRob(nums, 0, n - 1), dfsRob(nums, 1, n));
    }

    int dfsRob(int[] nums, int s, int e) {
        int n = nums.length - 1;
        int[] dp = new int[n + 2 + s];
        for (int i = s + 2; i < e + 2; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i - 2], dp[i - 1]);
        }
        return dp[n + 1 + s];
    }

    public void mainRobII(String[] args) {
        System.out.println(robII(new int[]{1, 2, 3, 1}));
    }

    /**
     * 按摩师
     * 不能接受相邻的预约，每个预约可以接受或者不接受
     * 动态规划
     * 如果dp[i]接受了，那么就不能在接受 dp[i-1] 或者是dp[i+1]的预约
     * 令dp[i]表示的是在i这个位置能获得的最大的时间数
     * dp[i] = max(dp[i-2] + n[i-2],dp[i-1])选当前位置或者不选
     * 如果后面有个无比大的数，那么也能选择到，所以后面的数对前面的选择没有影响 并不会因为前面的选择而导致无法选择到
     */
    public int massage(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 2];
        for (int i = 2; i < n + 2; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[n + 1];
    }

    /**
     * 地下城游戏 难度diff
     * 给你一个二维数组，也是从左上走到右下，但是这个数组中有正有负，需要返回走到这个右下需要的最小的值
     * 动态规划
     * 使用功能一个三维数组的额dp表 dp[m][n][2] dp[m][n][1]表示的是到这挑路径的最低健康值 dp[m][n][0]表示的是这个路径当前的健康值
     * 返回 [0]最低加 1
     * dp[i][j][1] = min(dp[i][j][0],dp[i][j][1])
     * dp[i][j][0] = max(dp[i-1][j][0],dp[i][j-1][0)
     * if dungon[i][j] < 0 dp[i][j][1]+dungon[i][j] else dp[i][j][1] + dungon[i][j]
     * dp多申请一行一列来防止越界 初始化为最小
     * 算法错误了 因为这是以i j位置为结尾的dp表，对于i j为位置的更新不能被ij之后的位置影响，而题目对于ij位置会有影响，所以推不出来
     * 而且只是ij表示的是从00到ij的最小，而不是到终点的最小，而终点的值会影响到ij的选择比如俩条路 [1,-2] [-1,-1] 而终点是 -2 如果每次都选
     * 最小值最大的这里-1 ，那么可以发现是错误的因为选 1，-2 只需要3的健康值 而-1，-1需要4的健康值，所以结果的正负对前面的选择造成了影响，所以推算
     * 出来的是错误的，而正确的需要是从ij开始走到终点，ij用来表示的ij到终点的最小健康值，这样就会选择1，-2，所以这样ij代表的才是正确的，因为他是在
     * 走到了终点之后对选择进行了判断
     * 所以不能以ij为结尾来推算
     * 正确解法
     * 应该是以某个位置为起点，然后使这个位置表示到达目的地所需的最低健康值
     * dp[i][j] 表示ij这个位置到达中的需要的最小健康值 那么对于这个起点会有俩种选择
     * 走到dp[i+1][j]或者dp[i][j+1]，而要走到这个地方，那么所需要的健康值x应该有
     * x + d[i][j] >= min(dp[i+1][j],dp[i][j+1]) ==> x >= min(dp[i+1][j],dp[i][j+1]) - d[i][j]
     * 有个特殊情况使x必须大于0,那么如果x小于了0，就取1
     * 在初始化的时候给右边下边多一行 并初始为MAXVALUE
     * 从尾开始填,递归超时了
     */
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];
        Arrays.fill(dp[m], Integer.MAX_VALUE);
        for (int i = 0; i < m + 1; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        dp[m][n - 1] = 0;

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, dp[i][j]);
            }
        }
        return dp[0][0];
    }

    public void mainCalculate(String[] args) {
        System.out.println(calculateMinimumHPPassHalf(new int[][]{{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}}));
        System.out.println(calculateMinimumHP(new int[][]{{0, 0, 0}, {1, 1, -1}}));
//        System.out.println(calculateMinimumHP(new int[][]{{1,-2,3}, {2,-2,-2}}));
        System.out.println(calculateMinimumHP(new int[][]{{1, -3, 3}, {0, -2, 0}, {-3, -3, -3}}));
        System.out.println(calculateMinimumHP(new int[][]{{100}}));
    }

    public int calculateMinimumHPOvertime(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m][n];
        dfsCalculate(dungeon, dp, m, n, 0, 0);
        return dp[0][0];
    }

    public int dfsCalculate(int[][] dungeon, int[][] dp, int m, int n, int i, int j) {
        int r = Integer.MAX_VALUE;
        int d = Integer.MAX_VALUE;
        if (i + 1 == m && j + 1 == n) {//走到了右下角就不需要往下走了
            dp[i][j] = -dungeon[i][j] + 1;
            dp[i][j] = Math.max(1, dp[i][j]);
            return dp[i][j];
        }
        if (i + 1 < m) {
            d = dfsCalculate(dungeon, dp, m, n, i + 1, j);
        }
        if (j + 1 < n) {
            r = dfsCalculate(dungeon, dp, m, n, i, j + 1);
        }
        dp[i][j] = Math.min(d, r) - dungeon[i][j];
        dp[i][j] = Math.max(1, dp[i][j]);
        return dp[i][j];
    }


    public int calculateMinimumHPPassHalf(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][][] dp = new int[m + 1][n + 1][2];
        for (int i = 0; i < m + 1; i++) {
            dp[i][n][1] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < n + 1; i++) {
            dp[n][i][1] = Integer.MAX_VALUE;
        }
        dp[m][n - 1][1] = 0;

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (dp[i + 1][j][1] < dp[i][j + 1][1]) {
                    dp[i][j][0] = dp[i + 1][j][0] + dungeon[i][j];
                    dp[i][j][1] = Math.min(dp[i][j][0], dp[i + 1][j][1]);
                } else {
                    dp[i][j][0] = dp[i][j + 1][0] + dungeon[i][j];
                    dp[i][j][1] = Math.min(dp[i][j][0], dp[i][j + 1][1]);
                }
            }
        }
        return -dp[0][0][1] + 1;
    }


    /**
     * 最小路径和
     * 给一个m*n的网格，其中包含非负的数字，一次只能向下或者向右，从左上走到右下找出一条数字和最小的路径
     * dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
     */
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        Arrays.fill(dp[0], Integer.MAX_VALUE);
        for (int i = 0; i < m + 1; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        dp[1][0] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }

    public void mainMinP(String[] args) {
        minPathSum(new int[][]{{1, 2, 3}, {4, 5, 6}});
    }

    /**
     * 下降路径最小和
     * 可以从第一行中随便选一个位置开始下降，每次下降只能选这个位置正对下面的连着的3的数字，返回最小和
     * 动态规划
     * dp[i][j]表示到这个位置的最小的下降和，最后遍历一下最后一行，选最小的就好了
     * dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+matrix[i][j]
     */
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        int maxN = Integer.MAX_VALUE;
        int[][] dp = new int[m + 1][n + 2];// 反正越界
        for (int i = 1; i < m + 1; i++) {
            dp[i][0] = maxN;
            dp[i][n + 1] = maxN;
        }
        int min = maxN;
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j <= m; j++) {
                int l = dp[i - 1][j - 1];
                int mid = dp[i - 1][j];
                int r = dp[i - 1][j + 1];
                dp[i][j] = Math.min(l, Math.min(mid, r)) + matrix[i - 1][j - 1];

                try {
                    if (i == m && min > dp[i][j]) {
                        min = dp[i][j];
                    }
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
            }
        }
        return min;
    }

    public void mainMinF(String[] args) {
        System.out.println(minFallingPathSum(new int[][]{{2, 1, 3}, {6, 5, 4}, {7, 8, 9}}));
    }

    /**
     * 珠宝的最大价值
     * 一个二维图中记录了珠宝的价值，从左上走到右下,每次只能向下或者向右，返回最大价值的路线
     * dp[i][j]表示的是走到这个未知的最大的礼物总数 那么就有
     * dp[i][j] = max(dp[i-1][j],dp[i][j-1])+frame[i][j]
     */
    public int jewelleryValue(int[][] frame) {
        int m = frame.length;
        int n = frame[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }

    /**
     * 不同路径II
     * 给定一个m*n的数组，一个机器人从左上走到右下，每次只能向右或者向下走，途中有不能经过的障碍，返回能走到终点的不同路径数量
     * 动态规划
     * dp[i][j]表示到i j这个位置的走法，如果这个为位置是个障碍，那走法就是为0
     * dp[i][j] = dp[i-1][j] + dp[i][j-1]
     * if obstacleGrid[i][j] == 1 那么 dp[i][j] = 0
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (obstacleGrid[i - 1][j - 1] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    public void mainEZZ(String[] args) {
        uniquePathsWithObstacles(new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}});
    }

    /**
     * 解法方式
     * 1-A 2-B   1 + @ = A
     * 给一段数字字符，可以通过数字来映射出字符，最终可以形成一个字符串，返回所有可能的结果
     * 动态规划
     * dp[i][0]表示的是i这么长的字符串编码1个字符有的结果的总数 dp[i][1]表示编码俩个字符有的总数 i,i-1，
     * 如果前一个使用了俩个字符编码那么后一个就不可使用俩个字符因为没有了 那么对于dp[i][j]就有
     * 如果i后一个为0，那么这就必须解码为俩个
     * dp[i][0] = dp[i-1][0] + dp[i-1][1]
     * dp[i][1] = dp[i-1][0]
     * 对与0需要额外考虑
     * 如果开始为0，那么就返回0
     * 如果当前为0，i-1就只能和i和为一起解码 还要确认这俩个是否和个合法的数字 比如30 就不合法
     * dp[i][0] = 0
     * dp[i][1] = dp[i-1][0]
     * 前置0 就不能和为俩个
     * dp[i][0] = dp[i-1][0] + dp[i-1][1]
     * dp[i][1] = 0
     * 没有后置0 因为我不知道后面的元素
     * 先默认数字都合法 好吧数字有不合法
     * 俩个数不合法的情况
     * 那么这个位置就不能使用俩个数编码
     * dp[i][0] = dp[i-1][0] + dp[i-1][0]
     * dp[i][1] = 0
     */

    public int numDecodings(String s) {
        if (s.charAt(0) == '0') {
            return 0;
        }
        int n = s.length();
        int[][] dp = new int[n + 1][2];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            //如果这个位置为0
            if (s.charAt(i - 1) == '0') {
                if (Integer.parseInt(s.charAt(i - 2) + "") > 2) {//这i-1为0 i-2的数大于了2，组不成一个合法的编码
                    return 0;
                }
                dp[i][0] = 0;
                dp[i][1] = dp[i - 1][0];
                continue;
            } else if (i - 1 >= 0 && s.charAt(i - 1) == '0') {//前置0
                dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
                dp[i][1] = 0; //表示这个位置没有使用俩个数字编码
                continue;
            }
            dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
            if (i - 2 < 0) {
                continue;
            } //这个数字是否合法
            StringBuilder tmp = new StringBuilder();
            tmp.append(s.charAt(i - 2));
            tmp.append(s.charAt(i - 1));
            if (Integer.parseInt(tmp.toString()) > 26) {
                dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
                dp[i][1] = 0;
                continue;
            }
            dp[i][1] = dp[i - 1][0];
        }
        return dp[n][0] + dp[n][1];
    }

    public void mainnumnDE(String[] args) {
        System.out.println('Z' - '@');
//        System.out.println(numDecodings("2101"));
    }

    /**
     * 使用最小花费爬楼梯
     * 花费cost[i]这些钱然后可以选择是走一步还是走俩步，最终使用最小花费走到终点
     * dp[i]表示到这里的最小的花费 那么就是 dp[i-1] +cost[i-1]和dp[i-2] +cost[i-2]的最小花费
     * 到i-1的最小在加上i-1的花费这样就能到i了
     */
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }

    /**
     * 三步问题
     * 有n个台阶，可以选择走一步，走俩步，走三步，计算有多少中上台阶的方式
     * 1 2 3 4
     * 1 2 4
     * 动态规划
     * dp[i]表示的是走到i阶梯的走法
     * 那么就有   dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
     * 最后一个阶梯走一步，俩步三步的走法都加上就是
     */
    public int waysToStep(int n) {
        if (n <= 3) {
            return n == 3 ? 4 : n;
        }
        long[] dp = new long[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return (int) (dp[n] % 1000000007);
    }

    // 动态规划专栏末尾
}
